package com.primaryAlgorithm;

/**
 * Description: 判断链表是不是回文的形式
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-09-26 00:29:23
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-09-26     张李鑫                     1.0         1.0 Version
 */
public class IsPalindrome {

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static boolean isPalindrome(ListNode listNode) {
        if (listNode.next == null) {
            return true;
        }
        ListNode mid = getMid(listNode);
        ListNode listNode1 = reverseNode(mid);

        while (listNode != null && listNode1 != null) {
            if (listNode.val != listNode1.val) {
                return false;
            }
            listNode = listNode.next;
            listNode1 = listNode1.next;
        }
        return true;
    }

    public static ListNode reverseNode(ListNode node) {
        ListNode oldNode = null;
        ListNode newNode = null;
        while (node != null) {
            newNode = node.next;
            node.next = oldNode;
            oldNode = node;
            node = newNode;
        }
        return oldNode;
    }

    /**
     * <p>
     * 如果是单数节点返回中间值的下一个节点
     * 如果是双数节点 也返回下一个
     * 把返回的链表从头节点开始反转 同步比较原链表 直到为null
     * </p>
     *
     * @param listNode
     * @return com.primaryAlgorithm.DeleteNode.ListNode
     * @Author zlx
     * @date 2021/9/26
     */
    public static ListNode getMid(ListNode listNode) {

        ListNode p1 = listNode;
        ListNode p2 = listNode;

        while (p2.next != null && p2.next.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1.next;
    }


    public static boolean isPalindrome(String s) {
        if (null == s) {
            return false;
        }

        int left = 0;
        int right = s.length() - 1;

        while (right > left) {

            while (right > left && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (right > left && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            if (Character.toTitleCase(s.charAt(right)) != Character.toTitleCase(s.charAt(left))) {
                return false;
            }
            left++;
            right--;
        }

        return true;
    }

    public static void main(String[] args) {
        String a = "race a car";
        boolean palindrome = isPalindrome(a);

        System.out.println(palindrome);
    }

}